package 树;

import java.util.TreeMap;

public class 红黑树 <K extends Comparable<K>,V>{

    public static boolean RED = true;

    public static boolean BLACK = false;

    Node root;

    public void put(K key,V value){
        root = doPut(root, key, value);
        root.color = BLACK;
    }

    public Node doPut(Node root,K key,V value){
        if (root == null){
            return new Node(key,value,1,RED);
        }
        int i = root.key.compareTo(key);

        if (i<0){
            root.left = doPut(root.left,key,value );
        }else if (i > 0){
            root.right = doPut(root.right,key,value );
        }else {
            root.value = value;
            return root;
        }
        return null;
    }

    public Node rotateLeft(Node root){
        Node right = root.right;
        root.right = right.left;
        right.left = root;
        right.color = root.color;
        root.color = RED;
        right.N = root.N;
        root.N = size(root);

        return right;
    }

    public int size(Node root){
        if (root == null){
            return 0;
        }
        return 1+size(root.left)+size(root.right);
    }



    public class Node<K extends Comparable<K>,V>{

        K key;

        V value;

        Node left;

        Node right;

        int N;

        boolean color;

        public Node(K key, V value, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
        }


    }
}
